package com.xucy.springboot.common.MustPrettyTree;

import java.util.*;

/**
 * @Author xucy
 * @Date 2019-04-17 17:30
 * @Description
 **/

public class TestYsNodeTree {
    public static void main(String[] args) {
        String str="can you can a can as a can canner can a can.";

        //进行赫夫曼树编码
        byte[] b=huffmanZip(str.getBytes());


        //进行赫夫曼树解码
        byte[] newByt=decode(buffCodes,b);
        System.out.println(new String(newByt));
    }

    //进行赫夫曼解码
    public static byte[] decode(Map<Byte, String> buffCodes, byte[] bs) {
        StringBuilder sb=new StringBuilder();
        //把byte数组转为一个二进制的字符串
        for(int i=0;i<bs.length;i++){
            if(i==bs.length-1){
                sb.append(byteToBitStr(false,bs[i]));
            }else{
                sb.append(byteToBitStr(true,bs[i]));
            }
        }

        System.out.println(sb);

        //把字符串按照指定的赫夫曼编码进行解码
        //把赫夫曼编码调换key value
        Map<String,Byte> newMap=new HashMap<>();
        for(Map.Entry<Byte,String> entry:buffCodes.entrySet()){
            newMap.put(entry.getValue(),entry.getKey());
        }

        List<Byte> byteList=new ArrayList<>();
        //处理字符串
        for(int i=0;i<sb.length();){
            int count=1;
            boolean flag=true;
            Byte b=null;
            while (flag) {
                String key=sb.substring(i,i+count);
                b=newMap.get(key);
                if(b==null){
                    count++;
                }else{
                    flag=false;
                }
            }
            System.out.println(b);
            byteList.add(b);
            i+=count;
        }

        //把集合转为数组
        byte[] b=new byte[byteList.size()];
        for(int i=0;i<byteList.size();i++){
            b[i]=byteList.get(i);
        }
        return b;
    }

    /**
     * 将得到的串进行补全 正数补0 负数取后8位
     *
     * @Author xucy
     * @Date 19:29 2019-04-17
     * @param
     * @return
     */
    public static  String byteToBitStr(boolean flag,byte b){
        int temp=b;
        if(flag){
            temp|=256;
        }
        String str=Integer.toBinaryString(temp);
        if(flag){
            return str.substring(str.length()-8);
        }else{
            return str;
        }


    }

    //进行赫夫曼树压缩的方法
    public static byte[] huffmanZip(byte[] bytes){
        //先统计每一个byte出现的次数，并放入到一个集合中
        List<YsNode> ysNodes=getList(bytes);
        //创建一颗赫夫曼树
        YsNode node=createHuffmanTree(ysNodes);

        //根据赫夫曼树获取赫夫曼编码表
        Map<Byte,String> buffCodes=getCodes(node);

        //进行赫夫曼编码
        byte[] bys=zip(bytes,buffCodes);
        return bys;
    }


    /**
     *进行赫夫曼编码
     *
     * @Author xucy
     * @Date 18:55 2019-04-17
     * @param
     * @return
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> buffCodes) {
        StringBuilder sb=new StringBuilder();
        //把需要压缩的数据转成二进制字符串
        for(byte b:bytes){
            sb.append(buffCodes.get(b));
        }
        System.out.println(sb);
        //定义长度
        int len;
        if(sb.length()%8==0){
            len=sb.length()/8;
        }else{
            len=sb.length()/8+1;
        }
        byte[] bys=new byte[len];
        int index=0;
        for (int i=0;i<sb.length();i+=8){
            String value="";
            if(i+8>sb.length()){
                value=sb.substring(i);
            }else{
                value=sb.substring(i,i+8);
            }
            byte bye=(byte) Integer.parseInt(value);
            bys[index]=bye;
            index++;
        }

        return bys;
    }

    //用于临时存储路径
    static StringBuilder sb=new StringBuilder();
    //存储赫夫曼编码
    static Map<Byte,String> buffCodes=new HashMap<>();
    //根据赫夫曼树获取赫夫曼编码
    private static Map<Byte, String> getCodes(YsNode node) {

        if(node==null){
            return null;
        }

        //向左路径追加"0"
        getCodes(node.leftNode,"0",sb);
        //向左路径追加"1"
        getCodes(node.rightNode,"1",sb);
        return buffCodes;
    }

    private static void getCodes(YsNode node, String code, StringBuilder sb) {

        StringBuilder sb2=new StringBuilder(sb);
        sb2.append(code);

        //如果等于null，说明不是叶子节点，需要继续在字符串中加路径
        if(node.data==null){
            getCodes(node.leftNode,"0",sb2);
            getCodes(node.rightNode,"1",sb2);
        }else{
            //不同的节点有不同的路径 如左边的左边"00" 左边的右边 "01"
            buffCodes.put(node.data,sb2.toString());
        }
    }

    //创建一颗赫夫曼树
    private static YsNode createHuffmanTree(List<YsNode> ysNodes) {

        while (ysNodes.size()>1){
            //先进行排序
            Collections.sort(ysNodes);
            //将最小的两个节点拿出来
            YsNode leftNode=ysNodes.get(ysNodes.size()-1);
            YsNode rightNode=ysNodes.get(ysNodes.size()-2);

            //生成新的节点
            YsNode parentNode=new YsNode(null,leftNode.weight+rightNode.weight);
            parentNode.leftNode=leftNode;
            parentNode.rightNode=rightNode;

            ysNodes.remove(leftNode);
            ysNodes.remove(rightNode);

            ysNodes.add(parentNode);
        }
        return ysNodes.get(0);
    }

    //将byte数组转为一个node集合
    public static  List<YsNode> getList(byte[] bytes){

        List<YsNode> ysNodes=new ArrayList<>();

        //存储每一个byte出现的次数
        Map<Byte,Integer> map=new HashMap();

        for (byte byt:bytes){
            Integer count=map.get(byt);
            if(count==null){
                map.put(byt,1);
            }else{
                map.put(byt,count+1);
            }
        }


        for (Map.Entry<Byte,Integer> entry:map.entrySet()){
            ysNodes.add(new YsNode(entry.getKey(),entry.getValue()));
        }

        return ysNodes;
    }
}
